Hydra

Memory limit: 128 MB

Little Bytie got a gift for his birthday. The gift contained a computer game called The Amazing Adventures of Knight Byteasar. The purpose of this game is to lead the knight through numerous challenges to defeat villains and evil witches and rescue damsels in distress.

Bytie managed to complete almost all levels of the game. Now he is stuck at the last level in which Byteasar needs to fight a giant serpent, the Bytean Hydra.

Byteasar will use his sword to fight the monster. Two sword strokes are available in the game. Byteasar can either cut off the serpent's head or slaughter the head (the latter stroke, obviously, requires more effort). Cutting the head off is simpler, however, it results in new heads growing back from the serpent's neck. Hydra is defeated only when it has no more heads and no new heads can grow back from its neck.

The Bytean Hydra may have types of heads that we number from to . In the beginning the serpent has one head of type 1. A head of type (for ) has the following characteristics: the number of sword swipes necessary to cut a head of this type off, , the number of sword swipes necessary to slaughter a head of this type, , and a list of types of heads that grow back in place of a head of this type if it is cut off, .

Help Bytie compute the minimum number of sword swipes that are necessary to defeat the Hydra.

Input

The first line of input contains one integer (), the number of types of heads of the Hydra. The following lines hold a description of the respective types of heads. The -th of those lines describes heads of type . It starts with three integers , , (, ) followed by a list of integers (). The sum of all 's does not exceed .

Output

The only line of output should contain one integer: the minimum number of sword swipes that are necessary to complete the game.

Example

For the input data:

4
4 27 3 2 3 2
3 5 1 2
1 13 2 4 2
5 6 1 2

the correct result is:

26

Task author: Tomasz Idziaszek.